//蠢方法，直接超时
fn rs_main1(strs: Vec<String>) -> Vec<Vec<String>> {
  use std::collections::HashMap;
  let mut result: Vec<Vec<String>> = Vec::new();
  if strs.len() == 0 { return result; }
  let mut used: Vec<bool> = vec![false; strs.len()];
  for i in 0..strs.len() {
    if used[i] { continue; }
    let mut temp: Vec<String> = Vec::new();
    temp.push(strs[i].clone());
    for j in i + 1..strs.len() {
      if used[j] { continue; }
      if strs[i].len() != strs[j].len() { continue; }
      let mut is_anagram = true;
      let mut map = HashMap::new();
      for char1 in strs[i].chars() {
        let count = map.entry(char1).or_insert(0);
        *count += 1;
      }
      for char2 in strs[j].chars() {
        let count = map.entry(char2).or_insert(0);
        *count -= 1;
        if *count < 0 {
          is_anagram = false;
          break;
        }
      }
      if is_anagram {
        used[j] = true;
        temp.push(strs[j].clone());
      }
    }
    result.push(temp);
  }
  return result;
}

// 使用字符ASCII码进行统计分析
fn rs_main2(strs: Vec<String>) -> Vec<Vec<String>> {
  use std::collections::HashMap;
  let mut result: Vec<Vec<String>> = Vec::new();
  if strs.len() == 0 { return result; }
  let mut map: HashMap<String, Vec<String>> = HashMap::new();
  let start_code = 'a' as usize;
  for i in 0..strs.len() {
    let mut count: [usize; 26] = [0; 26];
    for char in strs[i].chars() {
      count[char as usize - start_code] += 1;
    }
    let mut keys: Vec<String> = vec![];
    for i in 0..count.len() {
      keys.push(count[i].to_string() + "@");
    }
    let key: String = keys.into_iter().collect();
    let value = map.get(&key);
    if value.is_some() {
      let mut v = value.unwrap().to_vec();
      v.push(strs[i].clone());
      map.insert(key, v);
    } else {
      map.insert(key, vec![strs[i].clone()]);
    }
  }
  for value in map.values() {
    result.push(value.to_vec());
  }
  return result;
}

// 使用排序进行分析
fn rs_main3(strs: Vec<String>) -> Vec<Vec<String>> {
  use std::collections::HashMap;
  let mut result: Vec<Vec<String>> = Vec::new();
  if strs.len() == 0 { return result; }
  let mut map: HashMap<String, Vec<String>> = HashMap::new();
  for i in 0..strs.len() {
    let mut chars: Vec<char> = vec![];
    for char in strs[i].chars() {
      chars.push(char);
    }
    chars.sort();
    let key: String = chars.into_iter().collect();
    let value = map.get(&key);
    if value.is_some() {
      let mut v = value.unwrap().to_vec();
      v.push(strs[i].clone());
      map.insert(key, v);
    } else {
      map.insert(key, vec![strs[i].clone()]);
    }
  }
  for value in map.values() {
    result.push(value.to_vec());
  }
  return result;
}
/**
 * 最简洁的方式：
 *   1、使用字符ASCII码进行统计分析
 *   2、利用HashMap key可以接受数组作为对象的特性进行比较分析
 */
fn rs_main4(strs: Vec<String>) -> Vec<Vec<String>> {
  use std::collections::HashMap;
  let mut map = HashMap::new();
  for str in strs {
    let mut key = [0; 26];
    for char in str.as_bytes() {
      key[(char - 'a' as u8) as usize] += 1;
    }
    map.entry(key).or_insert(vec![]).push(str); // Rust的HashMap也可以接受非字符串或者数组作为key
  }
  map.values().map(|x| { x.clone() }).collect::<Vec<_>>()
}


fn main() {
  let test1 = vec![String::from("eat"), String::from("tea"), String::from("tan"), String::from("ate"), String::from("nat"), String::from("bat")];
  println!("{:?}", rs_main1(test1));
  println!("{:?}", rs_main1(vec![String::from("")]));
  println!("{:?}", rs_main1(vec![String::from("a")]));
  let test2 = vec![String::from("eat"), String::from("tea"), String::from("tan"), String::from("ate"), String::from("nat"), String::from("bat")];
  println!("{:?}", rs_main2(test2));
  println!("{:?}", rs_main2(vec![String::from("")]));
  println!("{:?}", rs_main2(vec![String::from("a")]));
  let test3 = vec![String::from("eat"), String::from("tea"), String::from("tan"), String::from("ate"), String::from("nat"), String::from("bat")];
  println!("{:?}", rs_main3(test3));
  println!("{:?}", rs_main3(vec![String::from("")]));
  println!("{:?}", rs_main3(vec![String::from("a")]));
  let test4 = vec![String::from("eat"), String::from("tea"), String::from("tan"), String::from("ate"), String::from("nat"), String::from("bat")];
  println!("{:?}", rs_main4(test4));
  println!("{:?}", rs_main4(vec![String::from("")]));
  println!("{:?}", rs_main4(vec![String::from("a")]));
}
